/**
 * 
 */
package No1_100.No91_100.BinaryTreeInorderTraversal_94;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/** 
 * @author  作者 E-mail: ttljtw@qq.com
 * @date 创建时间：2017年3月4日 下午4:08:42 
 * @version 1.0 
 * @parameter  
 * @since  
 * @return  
 */
/**
 * @author 李敬
 *
 */
public class Solution {

	/*
	 * 自己完成，按要求没有使用递归
	 * */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        if(root == null){
            return l;
        }
        Stack<TreeNode> s = new Stack<>();
        while(true){
            while(root!=null){
                s.push(root);
                root = root.left;
            }
            if(!s.empty()){////////////////判断栈为空的方法是empty()
                root = s.pop();
                l.add(root.val);
                root = root.right;
            }else{
                break;
            }
        }
        return l;
    }
    

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
